package me.mingshan.leetcode;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * https://leetcode.cn/problems/count-good-nodes-in-binary-tree/description/
 * <p>
 * 给你一棵根为 root 的二叉树，请你返回二叉树中好节点的数目。
 * <p>
 * 「好节点」X 定义为：从根到该节点 X 所经过的节点中，没有任何节点的值大于 X 的值。
 *
 * @author hanjuntao
 * @date 2025/8/29 0029
 */
public class L_1448_统计二叉树中好节点的数目 {


    public static void main(String[] args) {

        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(1);
        root.left.left = new TreeNode(3);
        root.right = new TreeNode(4);
        root.right.left = new TreeNode(1);
        root.right.right = new TreeNode(5);

        //          3
        //        1   4
        //     3     1  5

        System.out.println(goodNodes(root)); // 4

        TreeNode root2 = new TreeNode(2);
        root2.right = new TreeNode(4);
        root2.right.left = new TreeNode(10);
        root2.right.right = new TreeNode(8);
        root2.right.right.left = new TreeNode(4);
        System.out.println(goodNodes(root2)); // 4

    }

    /**
     * 利用dfs遍历，在处理一个路径时，
     * 判断当前元素之前是否存在大于当前元素的元素。
     *
     * 遍历路径采用dfs遍历，用list存储路径，在递归回溯时删除当前元素，保证下次递归时，使用空的list
     *
     * 使用HashSet存储结果，判断唯一性
     *
     * @param root
     * @return
     */
    public static int goodNodes(TreeNode root) {
        if (root == null) {
            return 0;
        }

        Set<TreeNode> result = new HashSet<>();
        result.add(root);

        dfs(root, new ArrayList<>(), result);

        return result.size();
    }

    private static void dfs(TreeNode root, List<TreeNode> s, Set<TreeNode> result) {
        if (root == null) {
            return;
        }

        boolean flag = true;
        // 判断当前元素之前是否存在大于当前元素的元素
        for (TreeNode treeNode : s) {
            if (treeNode.val > root.val) {
                flag = false;
            }
        }

        if (flag) {
            result.add(root);
        }

        s.add(root);

        if (root.left == null && root.right == null) {
            s.remove(s.size() - 1);
            return;
        }

        dfs(root.left, s, result);
        dfs(root.right, s, result);

        s.remove(s.size() - 1);
    }

    /**
     * 递归DFS（不使用额外空间）
     *
     * 当前树的总好节点数目 = 左子树好节点数目 + 右子树好节点数目 + （当前节点是否好节点 ？ 1 : 0）
     *
     * 如何判断当前节点是否好节点？
     * 由dfs 从根节点往子节点遍历可知，我们只要维护一个变量maxValue，记录当前子树的根节点到 root根节点之间的最大值。
     *
     * 这个很好维护，只需要在递归调用时，判断当前值与maxValue比较，如果大于maxValue，更新maxValue为当前值。
     * maxValue的初始值为根节点的值
     *
     * @param root
     * @return
     */
    public static int goodNodes2(TreeNode root) {
        return dfs2(root, Integer.MIN_VALUE);
    }

    private static int dfs2(TreeNode root, int maxValue) {
        if (root == null) {
            return 0;
        }

        int max = Math.max(maxValue, root.val);

        int left = dfs2(root.left, max);
        int right = dfs2(root.right, max);
        return (root.val >= maxValue ? 1 : 0) + left + right;
    }
}
